# coding=utf-8

"""
A linked list is given such that each node contains an additional random pointer which could point
to any node in the list or null.

Return a deep copy of the list.
"""

"""
solution:

因为是随机的指向其他结点 因此 顺序拷贝的时候 可能某个结点中的 random 指向的结点还没有被
copy 到 因此需要提前将其 记录到 一个dict中（保存的是 node对象）这样的话 最坏的情况

空间复杂度 O(n)
时间 O(n)


coolshell 的解法：

/*
 *
 *  The idea as below:
 *
 *  Consider we have a linked list as below:
 *
 *    node1->random = node2;
 *    node2->random = node1;
 *    node3->random = node1;
 *
 *       +-------------+
 *       |             v
 *    +-------+    +-------+    +-------+
 *    | node1 |----> node2 |----> node3 |--->NULL
 *    +-------+    +-------+    +-------+
 *      ^  ^           |           |
 *      |  +-----------+           |
 *      +--------------------------+
 *
 *
 *  To copy the list,
 *
 *    1) We insert a new node for each node's next position
 *
 *
 *       +-------------------------+
 *       |                         v
 *    +--+----+     +-----+    +-------+     +-----+    +-------+     +-----+
 *    | node1 |---> | NEW |----> node2 |---> | NEW |----> node3 |---> | NEW | ---> NULL
 *    +-------+     +-----+    +---+---+     +-----+    +--+----+     +-----+
 *      ^  ^                       |                       |
 *      |  +-----------------------+                       |
 *      +--------------------------------------------------+
 *
 *    2) Then, we can construt the new node's random pointer:
 *
 *        (node1->next) -> random  = (node1->random) -> next;
 *
 *    3) After we take out all of the "NEW" node to finish the copy.
 *
 */

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *p = NULL, *h=NULL, *t=NULL;
        if (head == NULL){
            return NULL;
        }

        //creat a new node for each node and insert its next
        p = head;
        while ( p != NULL){
            RandomListNode *node = new RandomListNode(p->label);
            node->next = p->next;
            p->next = node;
            p = node->next;
        }

        //copy random pointer for each new node
        p = head;
        while (p != NULL){
            if (p->random != NULL){
                p->next->random = p->random->next;
            }
            p = p->next->next;
        }

        //break to two list
        p = head;
        h = t = head->next;
        while ( p != NULL ){
            p->next = p->next->next;
            if (t->next!=NULL){
                t->next = t->next->next;
            }

            p = p->next;
            t = t->next;
        }

        return h;
    }
};


/*
 *  Considering we have a link as below:
 *
 *
 *       +-------------+
 *       |             v
 *    +-------+    +-------+    +-------+
 *    | node1 |----> node2 |----> node3 |--->NULL
 *    +-------+    +-------+    +-------+
 *      ^  ^           |           |
 *      |  +-----------+           |
 *      +--------------------------+
 *
 *  1) Using a map to store each node's random pointer's position
 *
 *      map[node1->random] = 1;
 *      map[node2->random] = 0;
 *      map[node3->random] = 0;
 *
 *  2) Clone the linked list (only consider the next pointer)
 *
 *      new1 --> new2 --> new3 --> NULL
 *
 *  3) Using an array to strore the order of the cloned linked-list
 *
 *      v[0] = &new1
 *      v[1] = &new2
 *      v[2] = &new3
 *
 *  4) Then we can clone the random pointers.
 *
 *      new->random = v [ map[node->random] ]
 *
 */
class MySolution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {

        RandomListNode *p = NULL, *h=NULL, *t=NULL;
        //using a map to store the random pointer's postion.
        map<RandomListNode*, int> m;
        //construct the map
        int pos =0;
        for ( p = head; p != NULL; p = p->next, pos++){
            m[p] = pos;
        }

        //clone the linked list  (only consider the next pointer)
        //and using a vector to store each node's postion.
        vector<RandomListNode*> v;
        for (p = head; p != NULL; p = p->next){
            RandomListNode *node = new RandomListNode(p->label);
            v.push_back(node);
            if (h==NULL){
                h = t = node;
            }else{
                t->next = node;
                t = node;
            }
        }

        //p => source link head
        //t => new link head
        //move the p and t synchronously, and
        //     t->random = vector[ map[p->random] ];
        for (t=h, p = head; t!=NULL && p!= NULL; p=p->next, t=t->next){
            if (p->random!=NULL) {
                pos = m[p->random];
                t->random = v[pos];
            }
        }

        return h;

    }
};
"""


def print_list(l1):
    list_str = ""

    while l1:
        list_str = "[%s:%s] ->" % (l1.label, l1.random.label if l1.random else None)
        print list_str,
        l1 = l1.next

    print "None",


class RandomListNode(object):
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None


class Solution:
    def copyRandomList(self, head):
        curr = head
        random_node_map = {}

        while curr is not None:
            # 如果 random 中结点不是空
            # 则保存到 random_node_map 中
            # 注意这里保存的不是结点 而是 pos
            curr = curr.next

        curr = head
        while curr is not None:
            # 遍历clone链表的主线
            pass

        # 遍历已经 clone 的链表 填充 random 指针


if __name__ == "__main__":
    node1 = RandomListNode(1)
    node2 = RandomListNode(2)
    node3 = RandomListNode(3)

    l1 = node1
    _l1 = l1
    l1.next = node2
    l1.random = node3
    l1 = l1.next
    l1.next = node3
    l1 = l1.next
    l1.random = node2

    print_list(_l1)
